
/*
Description:
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
	vector<int> searchRange0(vector<int>& nums, int target) 
	{
		int start = 0, end = nums.size(), mid, left, right;
		while (start < end) {
			mid = (start + end) / 2;
			if (nums[mid] >= target)
				end = mid;
			else
				start = mid + 1;
		}
		left = start;

		start = 0, end = nums.size();
		while (start < end) {
			mid = (start + end) / 2;
			if (nums[mid] > target)
				end = mid;
			else
				start = mid + 1;
		}
		right = start;
		return left == right ? vector<int> {-1, -1} : vector<int>{ left,right - 1 };
	}
	
	vector<int> searchRange(vector<int>& nums, int target) {
		vector<int> r{-1,-1};
		
		int half = 0;
		int left = 0;
		int right = nums.size();
		
		while (left <right)
		{	
			half = (left + right) / 2;
			if (nums[half] == target)
			{
				left = right = half;
				while((left >= 0) && (nums[left] == target))
				{					
					r[0] = left;
					left--;
				}				
				
				while((right < nums.size()) && (nums[right] == target))
				{
					r[1] = right;
					right++;
				}				
				break;
			}
			else
			{
				if ((left == half) || (right == half))
				{
					break;
				}
				if (nums[half] > target)
				{
					right = half;
				}
				else
				{
					left = half;
				}	
			}
			
		}
		
		return r;
	}
	//vector<int> searchRange(int A[], int n, int target) {
	//	int i = 0, j = n - 1;
	//	vector<int> ret(2, -1);
	//	// Search for the left one
	//	while (i < j)
	//	{
	//		int mid = (i + j) / 2;
	//		if (A[mid] < target) i = mid + 1;
	//		else j = mid;
	//	}
	//	if (A[i] != target) return ret;
	//	else ret[0] = i;

	//	// Search for the right one
	//	j = n - 1;  // We don't have to set i to 0 the second time.
	//	while (i < j)
	//	{
	//		int mid = (i + j) / 2 + 1;	// Make mid biased to the right
	//		if (A[mid] > target) j = mid - 1;
	//		else i = mid;				// So that this won't make the search range stuck.
	//	}
	//	ret[1] = j;
	//	return ret;
	//}
};

int _searchRange()
{
	vector<int> nums1 {5, 7, 7, 8, 8, 10};

	vector<int> nums = nums1;
	int target = 5;
	Solution solu;
	vector<int> range;

	range = solu.searchRange(nums, target);

	cout << "nums: " << endl;
	for (auto num : nums)
	{
		cout << num << " ";
	}
	cout << endl;
	cout << "range: " << range[0] << ":" << range[1] << endl;
	return 0;
}